The present invention relates generally to network switches, and more particularly to storage and recovery of address information in an address cache of a network switch.
Network switches commonly employ an address cache to facilitate the flow of data units from a source device to a destination device in a communications network. The address cache contains entries that indicate address information for various devices in the network such as computers and printers. In a technique known as "forwarding," the switch employs the address information to determine which port or ports to employ for transmission of a received data unit toward the destination device. Without the benefit of the address information the switch needs to transmit the data unit via every port in the switch in accordance with a technique known as "flooding" in order to assure that the data unit may be received by the destination device.
Caching requires a hash function that maps a search key to a cache line index. The cache line index is used to access the cache to perform a comparison of the search key to the cache tag. If a match is found, the cache data associated with the cache entry is returned. In a network switch, the search key is commonly a Media Access Control ("MAC") address. The cache tag is compared against the appropriate fields of the MAC address and if a match is found, the associated cache data is used to forward the data frame. The combination of cache line index and cache tag limit the amount of storage required for the data structure because the full 48 bit MAC address does not need to be stored in every cache entry.
Bit selection is one of the simplest forms of hash function. With bit selection, some number of bits (e.g., low order 16 bits of MAC address) are used as the cache line index and the remaining bits (e.g., high order 32 bits) are stored in the cache entry as the cache tag. A matching cache entry is found when the cache tag is equal to the corresponding bits of the MAC address for which the search is being performed.
In network switch applications the key space is the set of all MAC addresses and the search key space is the subset of MAC addresses that a given network switch will find encapsulated in the header of frames that it receives. An important aspect of any hash function is the degree to which it uniformly distributes the values from the search key space in the hash key space. The hash key space is the set of all cache line indices generated from the hash function. If the search key space included all possible MAC addresses, then a simple bit select function would likely suffice because the values in the search key space would uniformly alias in the hash key space.
In practical application, however, the search key space has been demonstrated to contain more information in the low order 28 bits of each value than in the high order 20 bits. This property is developed in the paper "A Comparison of Hashing Schemes for Address Lookup in Computer Networks," Raj Jain, IEEE Transactions on Communication, Vol. 40, Number 3, October 1992. It is reasonable to expect some variation in this bit position information content among different network switches since the search key space may be different for each switch. However, the conclusion reached by Jain remains applicable. A desirable hash is one that uniformly distributes search keys in the hash space, permits storage of less than the full MAC address in each cache entry, and can be adapted to variations in the search key space.